package com.example.targetOffer.controller;

import java.util.Random;

/**
 * 动态规划之 寻找最优子结构
 */
public class DP_02 {

    public static void main(String[] args) {

        int[] array = {2,2,2,0,1};
        int value = minArray(array);
        System.out.println(value);
    }

    public static int minArray(int[] numbers) {
        quickSort(numbers, 0 , numbers.length -1);
        return numbers[0];
    }

    private static void quickSort(int[] numbers, int low, int high){
        if(low < high) {
            //主逻辑, 每一轮都将将基准元素送到最终位置
            int pivotIndex = split(numbers, low, high);

            //递归. 左、右分治
            quickSort(numbers, low, pivotIndex - 1);
            quickSort(numbers, pivotIndex + 1, high);
        }
    }

    private static int split(int[] numbers, int low, int high) {


        int start = low;
        int pivotValue = numbers[start];

        //使用递推的方式,使所有小于pivot的在左边, 所有大于pivot的在右边

        //出口为low=high, 当low=high时, 代表我们基准元素已经到了其最终位置了
        while(low < high) {

            //要注意high和low的值一直在变化当中, 所以每一步操作前都必须验证 low是否小于high

            //先从high开始比较与移动. 若high所指对象比基准值大或等,则不用交换, 直接向前移动
            while(low < high && numbers[high] >= pivotValue) {
                high--;
            }

            //再从high开始比较与移动. 若low所指对象比基准值小或等,则不用交换, 直接向后移动
            while(low < high && numbers[low] <= pivotValue) {
                low++;
            }

            if(low >= high) break;

            //到了此处,说明low所指对象 > pivot, high所指对象 < pivot, 所以交换两者
            swap(numbers, low, high);
        }

        //while循环后, low = high; 且已按照基准值左小右大的要求排列好
        //且 low/high 现在所指的位置就是基准值应该在的问题, 所以别忘了基准值要归位
        swap(numbers, start, low);

        //返回基准值所在位置
        return low;
    }

    private static void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }



}
